package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         51,
		Discription: "N皇后II",
		Level:       3,
		Labels: map[string]int{
			"哈希表": 1,
			"回溯":  1,
			"递归":  1,
			"类数独": 1,
		},
	})
}

func TotalNQueens(n int) int {
	rows := make([]bool, n)
	slash1 := make([]bool, 2*n+1)
	slash2 := make([]bool, 2*n+1)

	count := 0
	var search func(int)
	search = func(column int) {
		if column == n {
			count++
			return
		}

		for j := 0; j < n; j++ {
			if rows[j] || slash1[column+j] || slash2[column-j+n-1] {
				continue
			}

			rows[j] = true
			slash1[column+j] = true
			slash2[column-j+n-1] = true
			search(column + 1)
			rows[j] = false
			slash1[column+j] = false
			slash2[column-j+n-1] = false
		}
	}

	search(0)
	return count
}
